Multiplying two polynomials (or integers) efficiently is a key issue in a variety of academic fields and practical applications. Examples of such fields and applications include (but are not limited to): signal processing, cryptography, digital security systems, computer science, and number theory.
Multiplication—Classic Schoolbook Style
The conventional (i.e., “classic schoolbook” style) of multiplication in positional number systems requires approximately c*m*n operations to multiply an m-place (e.g., m-digits) number by an n-place (e.g., n-digits) number, for some constant c. When m=n, this conventional procedure for multiplication of two n-place numbers requires an execution time approximately proportional to n2, as n increases. This cost is sometimes written O(n2).
Put another way, this classic schoolbook approach of multiplication of two n-digit numbers results in a cost of n2 operations. The overall cost of the big multiplication is the number of basic operations (e.g., addition, subtraction, and multiplication of single-digit numbers) required to complete a task; however, often the focus is on the multiplication tasks since those typically dominate the running time. The task in this case is the multiplication of two n-digit numbers.
This conventional multiplication approach has many different names. For example, it may be called “brute-force”, “long”, “classic”, and such. Herein, it is referred to as “classic schoolbook” multiplication.
It is also used for the multiplication of polynomials. For example, let n be a positive integer. The “classic schoolbook” way to multiply two univariate polynomials of degree at most n−1 (i.e., with n terms each, some of whose coefficients may be zero) needs n2 multiplications of coefficients. It multiplies each coefficient of one polynomial by each coefficient of the other, adding the products where needed.
If a(X)=a1X+a0 and b(X)=b1X+b0 are two linear polynomials in the same variable X, then the “classic schoolbook” approach computes all three coefficients of the product polynomial a(X)b(X)=a1b1X2+(a1b0+a0b1)X+a0b0 with four multiplications of the original coefficients, followed by one addition. As discussed later, other approaches need only three coefficient multiplications.
Fast Multiplication—Karatsuba Style
In 1962, A. Karatsuba and Yu. Ofman suggested (in Doklady Akad. Nauk SSSR 145 (1963), 293-294) a new multiplication technique that had an overall asymptotic cost less than the classic schoolbook's O(n2). Since 1962, many variants of Karatsuba have been proposed. This is described further by Donald E. Knuth in his “The Art of Computer Programming”, Volume 2, Seminumerical Algorithms, Third Edition, Addison-Wesley 1998). More on the Karatsuba-style multiplication appears in “Generalizations of the Karatsuba Algorithm for Efficient Implementations” by André Weimerskirch and Christof Paar (http://www.crypto.ruhr-uni-bochum.de/Publikationen/texte/kaweb.pdf).
In terms of efficiency, the Karatsuba-style multiplication approach (with its existing variants) is an improvement over the classic schoolbook approach. Just like back in 1962 when Karatsuba suggested a new approach, it is still desirable to improve the efficiency (and thus speed) of multiplication.